// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"strings"
)

func frequencySort(s string) string {
	return bucketSort(s)
}

func bucketSort(s string) string {
	// 以相同频率存储rune的桶
	bucket := make([][]rune, len(s)+1)
	m := make(map[rune]int)
	result := ""

	for _, r := range s {
		m[r] += 1
	}
	for r, time := range m {
		bucket[time] = append(bucket[time], r)
	}
	for i := len(s); i >= 0; i-- {
		for _, r := range bucket[i] {
			result += strings.Repeat(string(r), i)
		}
	}
	return result
}

func main() {
	str := "ILoveGo"
	res := frequencySort(str)
	fmt.Println(res)
}

//$ go run interview6-15.go
//ooLveGI
